package test;

import java.util.ArrayList;
import java.util.List;

public class PlanTree {
    public static void main(String[] args) {
        int n = 3;
        int m = 3;
        int[][] arr = {{0,1,1},{1,1,0},{1,1,1}};
//        int[][] arr = {{0,1,1}};
        int[][] res = new  int[n][m];
        List<Integer> result = new ArrayList<>();
        planTree(0,n,m,arr,res,result);
        System.out.println(result.size());

    }

    private static void planTree(int current, int n, int m  , int[][] arr, int[][] res,List<Integer> result) {
        if(n < 1 || m < 1){
            return;
        }
        if (arr == null){
            return;
        }
        int num = n * m;
        if (current >= num ){
            result.add(1);
            return;
        }
        int row = current / m;
        int column = current % (m - 1);
        for (int i = 1;i <= 3; i++){ // 1 ：种树 2： 不种
            if (i == 3){
                return;
            }
            if (isLegal(row,column,arr,res,i)){
                res[row][column] = i;
                planTree(current + 1,n,m,arr,res,result);
                res[row][column] = 0;
            }
        }
    }

    private static boolean isLegal(int row, int column,int[][] arr, int[][] res, int i) {
        if (arr[row][column] != 0){
            if (i == 1){
                if (row - 1 >= 0 && res[row - 1][column] == 1){
                    return false;
                }else if (column - 1 >= 0 && res[row][column - 1] == 1){
                    return false;
                }else {
                    return true;
                }
            }else{
                return true;
            }
        }else {
            if (i == 2){
                return true;
            }
        }
        return false;
    }
}
